/**
 * Created with IntelliJ IDEA.
 * Description:链表的奇偶重排
 * User: wangxin
 * Date: 2024-10-30
 * Time: 19:09
 */

import java.util.*;


   class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }

public class test1 {
       //方法一
        public ListNode oddEvenList (ListNode head) {
            // write code here
            if(head == null){
                return null;
            }
            ListNode h1 = new ListNode(-1);
            ListNode h2 = new ListNode(-4);
            ListNode h11 = h1;
            ListNode h22 = h2;
            int i = 1;
            ListNode cur = head;
            while(cur != null){
                if(i % 2 == 1){
                    h11.next = cur;
                    h11 = h11.next;
                }
                else{
                    h22.next = cur;
                    h22 = h22.next;
                }
                cur = cur.next;
                i++;
            }
            h11.next  = h2.next;
            h22.next = null;

            return h1.next;
        }
        //方法二
        public ListNode oddEvenList2 (ListNode head) {
            // write code here
            if(head == null){
                return head;
            }
            ListNode even  = head .next;
            ListNode odd = head ;
            ListNode h = even;
            while(even != null&&even.next != null){

                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;

            }
            odd.next = h;
            return head ;
        }

}
